package binarySortTree;

public class BinarySortTree {
    private Node root;

    public BinarySortTree(Node root) {
        this.root = root;
    }
     /*
    中序遍历
     */
     public void infixOrder(Node root){
         if (root!=null){
             root.infixOrder(root);
         }
     }
    /*
    添加节点
     */
    public void addNode(Node node){
        if(node !=null){
            root.addNode(node);
        }
    }
    /*
    获取删除的节点
     */
    public Node delNode(int val){
       return  root.delNode(val);
    }
    /*
    获取删除节点的父节点
     */
    public Node delParentNode(int val){
       return root.delParentNode(val);
    }

    public int rightTreeMin(Node node){
        //第一种情况
        Node target = node;
        while(target.getLeft()!=null){
            target = target.getLeft();
        }
        delNode2(target.getVal());
        return target.getVal();
    }
    /*
    删除节点
     */
    public void delNode2(int val){
        Node target = delNode(val);
        if(target==null){
            return;
        }
        Node parentNode = delParentNode(val);
        //1.叶子节点
        if(target.getLeft()==null&&target.getRight()==null){
            if(target==parentNode.getLeft()){
                parentNode.setLeft(null);
            }
            if(target==parentNode.getRight()){
                parentNode.setRight(null);
            }
        }//具有双孩子的节点
        else if(target.getLeft()!=null&&target.getRight()!=null){
            int min = rightTreeMin(target.getRight());
            parentNode.setVal(min);
        }else{//只有一个树
            if(target.getLeft()!=null){
                if(parentNode!=null){
                    if(parentNode.getLeft().getVal()==val){
                        parentNode.setLeft(target.getLeft());
                    }else{
                        parentNode.setRight(target.getLeft());
                    }
                }else{
                    root = target.getLeft();
                }
            }else{
                if(parentNode!=null){
                    if(parentNode.getLeft().getVal()==val){
                        parentNode.setLeft(target.getRight());
                    }else{
                        parentNode.setRight(target.getRight());
                    }
                }
            }
        }
    }
}
